home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 1.iso / toolbox / src / demos / OpenGL / puzzle / puzzle.c < prev    next >
C/C++ Source or Header  |  1996-11-11  |  31KB  |  1,473 lines
  1. /*
  2.  * (c) Copyright 1993, 1994, Silicon Graphics, Inc.
  3.  * ALL RIGHTS RESERVED
  4.  * Permission to use, copy, modify, and distribute this software for
  5.  * any purpose and without fee is hereby granted, provided that the above
  6.  * copyright notice appear in all copies and that both the copyright notice
  7.  * and this permission notice appear in supporting documentation, and that
  8.  * the name of Silicon Graphics, Inc. not be used in advertising
  9.  * or publicity pertaining to distribution of the software without specific,
  10.  * written prior permission.
  11.  *
  12.  * THE MATERIAL EMBODIED ON THIS SOFTWARE IS PROVIDED TO YOU "AS-IS"
  13.  * AND WITHOUT WARRANTY OF ANY KIND, EXPRESS, IMPLIED OR OTHERWISE,
  14.  * INCLUDING WITHOUT LIMITATION, ANY WARRANTY OF MERCHANTABILITY OR
  15.  * FITNESS FOR A PARTICULAR PURPOSE.  IN NO EVENT SHALL SILICON
  16.  * GRAPHICS, INC.  BE LIABLE TO YOU OR ANYONE ELSE FOR ANY DIRECT,
  17.  * SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY
  18.  * KIND, OR ANY DAMAGES WHATSOEVER, INCLUDING WITHOUT LIMITATION,
  19.  * LOSS OF PROFIT, LOSS OF USE, SAVINGS OR REVENUE, OR THE CLAIMS OF
  20.  * THIRD PARTIES, WHETHER OR NOT SILICON GRAPHICS, INC.  HAS BEEN
  21.  * ADVISED OF THE POSSIBILITY OF SUCH LOSS, HOWEVER CAUSED AND ON
  22.  * ANY THEORY OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE
  23.  * POSSESSION, USE OR PERFORMANCE OF THIS SOFTWARE.
  24.  *
  25.  * US Government Users Restricted Rights
  26.  * Use, duplication, or disclosure by the Government is subject to
  27.  * restrictions set forth in FAR 52.227.19(c)(2) or subparagraph
  28.  * (c)(1)(ii) of the Rights in Technical Data and Computer Software
  29.  * clause at DFARS 252.227-7013 and/or in similar or successor
  30.  * clauses in the FAR or the DOD or NASA FAR Supplement.
  31.  * Unpublished-- rights reserved under the copyright laws of the
  32.  * United States.  Contractor/manufacturer is Silicon Graphics,
  33.  * Inc., 2011 N.  Shoreline Blvd., Mountain View, CA 94039-7311.
  34.  *
  35.  * OpenGL(TM) is a trademark of Silicon Graphics, Inc.
  36.  */
  37. #include <stdio.h>
  38. #include <stdlib.h>
  39. #include <string.h>
  40. #include <sys/types.h>
  41. #include <malloc.h>
  42. #include <time.h>
  43. #include <math.h>
  44. #include <GL/glut.h>
  45. #include "trackball.h"
  46.  
  47. #define WIDTH 4
  48. #define HEIGHT 5
  49. #define PIECES 10
  50. #define OFFSETX -2
  51. #define OFFSETY -2.5
  52. #define OFFSETZ -0.5
  53.  
  54. typedef char Config[HEIGHT][WIDTH];
  55.  
  56. struct puzzle {
  57.   struct puzzle *backptr;
  58.   struct puzzle *solnptr;
  59.   Config pieces;
  60.   struct puzzle *next;
  61.   unsigned hashvalue;
  62. };
  63.  
  64. #define HASHSIZE 10691
  65.  
  66. struct puzzlelist {
  67.   struct puzzle *puzzle;
  68.   struct puzzlelist *next;
  69. };
  70.  
  71. static char convert[PIECES + 1] =
  72. {0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4};
  73.  
  74. static unsigned char colors[PIECES + 1][3] =
  75. {
  76.   {0, 0, 0},
  77.   {255, 255, 127},
  78.   {255, 255, 127},
  79.   {255, 255, 127},
  80.   {255, 255, 127},
  81.   {255, 127, 255},
  82.   {255, 127, 255},
  83.   {255, 127, 255},
  84.   {255, 127, 255},
  85.   {255, 127, 127},
  86.   {255, 255, 255},
  87. };
  88.  
  89. void changeState(void);
  90.  
  91. static struct puzzle *hashtable[HASHSIZE];
  92. static struct puzzle *startPuzzle;
  93. static struct puzzlelist *puzzles;
  94. static struct puzzlelist *lastentry;
  95.  
  96. int curX, curY, visible;
  97.  
  98. #define MOVE_SPEED 0.2
  99. static unsigned char movingPiece;
  100. static float move_x, move_y;
  101. static float curquat[4];
  102. static int doubleBuffer = 1;
  103. static int depth = 1;
  104.  
  105. static char xsize[PIECES + 1] =
  106. {0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2};
  107. static char ysize[PIECES + 1] =
  108. {0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2};
  109. static float zsize[PIECES + 1] =
  110. {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.6};
  111.  
  112. static Config startConfig =
  113. {
  114.   {8, 10, 10, 7},
  115.   {8, 10, 10, 7},
  116.   {6, 9, 9, 5},
  117.   {6, 4, 3, 5},
  118.   {2, 0, 0, 1}
  119. };
  120.  
  121. static Config thePuzzle =
  122. {
  123.   {8, 10, 10, 7},
  124.   {8, 10, 10, 7},
  125.   {6, 9, 9, 5},
  126.   {6, 4, 3, 5},
  127.   {2, 0, 0, 1}
  128. };
  129.  
  130. static int xadds[4] =
  131. {-1, 0, 1, 0};
  132. static int yadds[4] =
  133. {0, -1, 0, 1};
  134.  
  135. static long W = 400, H = 300;
  136. static GLint viewport[4];
  137.  
  138. #define srandom srand
  139. #define random() (rand() >> 2)
  140.  
  141. unsigned
  142. hash(Config config)
  143. {
  144.   int i, j, value;
  145.  
  146.   value = 0;
  147.   for (i = 0; i < HEIGHT; i++) {
  148.     for (j = 0; j < WIDTH; j++) {
  149.       value = value + convert[config[i][j]];
  150.       value *= 6;
  151.     }
  152.   }
  153.   return (value);
  154. }
  155.  
  156. int
  157. solution(Config config)
  158. {
  159.   if (config[4][1] == 10 && config[4][2] == 10)
  160.     return (1);
  161.   return (0);
  162. }
  163.  
  164. float boxcoords[][3] =
  165. {
  166.   {0.2, 0.2, 0.9},
  167.   {0.8, 0.2, 0.9},
  168.   {0.8, 0.8, 0.9},
  169.   {0.2, 0.8, 0.9},
  170.   {0.2, 0.1, 0.8},
  171.   {0.8, 0.1, 0.8},
  172.   {0.9, 0.2, 0.8},
  173.   {0.9, 0.8, 0.8},
  174.   {0.8, 0.9, 0.8},
  175.   {0.2, 0.9, 0.8},
  176.   {0.1, 0.8, 0.8},
  177.   {0.1, 0.2, 0.8},
  178.   {0.2, 0.1, 0.2},
  179.   {0.8, 0.1, 0.2},
  180.   {0.9, 0.2, 0.2},
  181.   {0.9, 0.8, 0.2},
  182.   {0.8, 0.9, 0.2},
  183.   {0.2, 0.9, 0.2},
  184.   {0.1, 0.8, 0.2},
  185.   {0.1, 0.2, 0.2},
  186.   {0.2, 0.2, 0.1},
  187.   {0.8, 0.2, 0.1},
  188.   {0.8, 0.8, 0.1},
  189.   {0.2, 0.8, 0.1},
  190. };
  191.  
  192. float boxnormals[][3] =
  193. {
  194.   {0, 0, 1},            /* 0 */
  195.   {0, 1, 0},
  196.   {1, 0, 0},
  197.   {0, 0, -1},
  198.   {0, -1, 0},
  199.   {-1, 0, 0},
  200.   {0.7071, 0.7071, 0.0000},  /* 6 */
  201.   {0.7071, -0.7071, 0.0000},
  202.   {-0.7071, 0.7071, 0.0000},
  203.   {-0.7071, -0.7071, 0.0000},
  204.   {0.7071, 0.0000, 0.7071},  /* 10 */
  205.   {0.7071, 0.0000, -0.7071},
  206.   {-0.7071, 0.0000, 0.7071},
  207.   {-0.7071, 0.0000, -0.7071},
  208.   {0.0000, 0.7071, 0.7071},  /* 14 */
  209.   {0.0000, 0.7071, -0.7071},
  210.   {0.0000, -0.7071, 0.7071},
  211.   {0.0000, -0.7071, -0.7071},
  212.   {0.5774, 0.5774, 0.5774},  /* 18 */
  213.   {0.5774, 0.5774, -0.5774},
  214.   {0.5774, -0.5774, 0.5774},
  215.   {0.5774, -0.5774, -0.5774},
  216.   {-0.5774, 0.5774, 0.5774},
  217.   {-0.5774, 0.5774, -0.5774},
  218.   {-0.5774, -0.5774, 0.5774},
  219.   {-0.5774, -0.5774, -0.5774},
  220. };
  221.  
  222. int boxfaces[][4] =
  223. {
  224.   {0, 1, 2, 3},         /* 0 */
  225.   {9, 8, 16, 17},
  226.   {6, 14, 15, 7},
  227.   {20, 23, 22, 21},
  228.   {12, 13, 5, 4},
  229.   {19, 11, 10, 18},
  230.   {7, 15, 16, 8},       /* 6 */
  231.   {13, 14, 6, 5},
  232.   {18, 10, 9, 17},
  233.   {19, 12, 4, 11},
  234.   {1, 6, 7, 2},         /* 10 */
  235.   {14, 21, 22, 15},
  236.   {11, 0, 3, 10},
  237.   {20, 19, 18, 23},
  238.   {3, 2, 8, 9},         /* 14 */
  239.   {17, 16, 22, 23},
  240.   {4, 5, 1, 0},
  241.   {20, 21, 13, 12},
  242.   {2, 7, 8, -1},        /* 18 */
  243.   {16, 15, 22, -1},
  244.   {5, 6, 1, -1},
  245.   {13, 21, 14, -1},
  246.   {10, 3, 9, -1},
  247.   {18, 17, 23, -1},
  248.   {11, 4, 0, -1},
  249.   {20, 12, 19, -1},
  250. };
  251.  
  252. #define NBOXFACES (sizeof(boxfaces)/sizeof(boxfaces[0]))
  253.  
  254. /* Draw a box.  Bevel as desired. */
  255. void
  256. drawBox(int piece, float xoff, float yoff)
  257. {
  258.   int xlen, ylen;
  259.   int i, k;
  260.   float x, y, z;
  261.   float zlen;
  262.   float *v;
  263.  
  264.   xlen = xsize[piece];
  265.   ylen = ysize[piece];
  266.   zlen = zsize[piece];
  267.  
  268.   glColor3ubv(colors[piece]);
  269.   glBegin(GL_QUADS);
  270.   for (i = 0; i < 18; i++) {
  271.     glNormal3fv(boxnormals[i]);
  272.     for (k = 0; k < 4; k++) {
  273.       if (boxfaces[i][k] == -1)
  274.         continue;
  275.       v = boxcoords[boxfaces[i][k]];
  276.       x = v[0] + OFFSETX;
  277.       if (v[0] > 0.5)
  278.         x += xlen - 1;
  279.       y = v[1] + OFFSETY;
  280.       if (v[1] > 0.5)
  281.         y += ylen - 1;
  282.       z = v[2] + OFFSETZ;
  283.       if (v[2] > 0.5)
  284.         z += zlen - 1;
  285.       glVertex3f(xoff + x, yoff + y, z);
  286.     }
  287.   }
  288.   glEnd();
  289.   glBegin(GL_TRIANGLES);
  290.   for (i = 18; i < NBOXFACES; i++) {
  291.     glNormal3fv(boxnormals[i]);
  292.     for (k = 0; k < 3; k++) {
  293.       if (boxfaces[i][k] == -1)
  294.         continue;
  295.       v = boxcoords[boxfaces[i][k]];
  296.       x = v[0] + OFFSETX;
  297.       if (v[0] > 0.5)
  298.         x += xlen - 1;
  299.       y = v[1] + OFFSETY;
  300.       if (v[1] > 0.5)
  301.         y += ylen - 1;
  302.       z = v[2] + OFFSETZ;
  303.       if (v[2] > 0.5)
  304.         z += zlen - 1;
  305.       glVertex3f(xoff + x, yoff + y, z);
  306.     }
  307.   }
  308.   glEnd();
  309. }
  310.  
  311. float containercoords[][3] =
  312. {
  313.   {-0.1, -0.1, 1.0},
  314.   {-0.1, -0.1, -0.1},
  315.   {4.1, -0.1, -0.1},
  316.   {4.1, -0.1, 1.0},
  317.   {1.0, -0.1, 0.6},     /* 4 */
  318.   {3.0, -0.1, 0.6},
  319.   {1.0, -0.1, 0.0},
  320.   {3.0, -0.1, 0.0},
  321.   {1.0, 0.0, 0.0},      /* 8 */
  322.   {3.0, 0.0, 0.0},
  323.   {3.0, 0.0, 0.6},
  324.   {1.0, 0.0, 0.6},
  325.   {0.0, 0.0, 1.0},      /* 12 */
  326.   {4.0, 0.0, 1.0},
  327.   {4.0, 0.0, 0.0},
  328.   {0.0, 0.0, 0.0},
  329.   {0.0, 5.0, 0.0},      /* 16 */
  330.   {0.0, 5.0, 1.0},
  331.   {4.0, 5.0, 1.0},
  332.   {4.0, 5.0, 0.0},
  333.   {-0.1, 5.1, -0.1},    /* 20 */
  334.   {4.1, 5.1, -0.1},
  335.   {4.1, 5.1, 1.0},
  336.   {-0.1, 5.1, 1.0},
  337. };
  338.  
  339. float containernormals[][3] =
  340. {
  341.   {0, -1, 0},
  342.   {0, -1, 0},
  343.   {0, -1, 0},
  344.   {0, -1, 0},
  345.   {0, -1, 0},
  346.   {0, 1, 0},
  347.   {0, 1, 0},
  348.   {0, 1, 0},
  349.   {1, 0, 0},
  350.   {1, 0, 0},
  351.   {1, 0, 0},
  352.   {-1, 0, 0},
  353.   {-1, 0, 0},
  354.   {-1, 0, 0},
  355.   {0, 1, 0},
  356.   {0, 0, -1},
  357.   {0, 0, -1},
  358.   {0, 0, 1},
  359.   {0, 0, 1},
  360.   {0, 0, 1},
  361.   {0, 0, 1},
  362.   {0, 0, 1},
  363.   {0, 0, 1},
  364.   {0, 0, 1},
  365. };
  366.  
  367. int containerfaces[][4] =
  368. {
  369.   {1, 6, 4, 0},
  370.   {0, 4, 5, 3},
  371.   {1, 2, 7, 6},
  372.   {7, 2, 3, 5},
  373.   {16, 19, 18, 17},
  374.  
  375.   {23, 22, 21, 20},
  376.   {12, 11, 8, 15},
  377.   {10, 13, 14, 9},
  378.  
  379.   {15, 16, 17, 12},
  380.   {2, 21, 22, 3},
  381.   {6, 8, 11, 4},
  382.  
  383.   {1, 0, 23, 20},
  384.   {14, 13, 18, 19},
  385.   {9, 7, 5, 10},
  386.  
  387.   {12, 13, 10, 11},
  388.  
  389.   {1, 20, 21, 2},
  390.   {4, 11, 10, 5},
  391.  
  392.   {15, 8, 19, 16},
  393.   {19, 8, 9, 14},
  394.   {8, 6, 7, 9},
  395.   {0, 3, 13, 12},
  396.   {13, 3, 22, 18},
  397.   {18, 22, 23, 17},
  398.   {17, 23, 0, 12},
  399. };
  400.  
  401. #define NCONTFACES (sizeof(containerfaces)/sizeof(containerfaces[0]))
  402.  
  403. /* Draw the container */
  404. void
  405. drawContainer(void)
  406. {
  407.   int i, k;
  408.   float *v;
  409.  
  410.   /* Y is reversed here because the model has it reversed */
  411.  
  412.   /* Arbitrary bright wood-like color */
  413.   glColor3ub(209, 103, 23);
  414.   glBegin(GL_QUADS);
  415.   for (i = 0; i < NCONTFACES; i++) {
  416.     v = containernormals[i];
  417.     glNormal3f(v[0], -v[1], v[2]);
  418.     for (k = 3; k >= 0; k--) {
  419.       v = containercoords[containerfaces[i][k]];
  420.       glVertex3f(v[0] + OFFSETX, -(v[1] + OFFSETY), v[2] + OFFSETZ);
  421.     }
  422.   }
  423.   glEnd();
  424. }
  425.  
  426. void
  427. drawAll(void)
  428. {
  429.   int i, j;
  430.   int piece;
  431.   char done[PIECES + 1];
  432.   float m[4][4];
  433.  
  434.   build_rotmatrix(m, curquat);
  435.   glMatrixMode(GL_MODELVIEW);
  436.   glLoadIdentity();
  437.   glTranslatef(0, 0, -10);
  438.   glMultMatrixf(&(m[0][0]));
  439.   glRotatef(180, 0, 0, 1);
  440.  
  441.   if (depth) {
  442.     glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
  443.   } else {
  444.     glClear(GL_COLOR_BUFFER_BIT);
  445.   }
  446.   for (i = 1; i <= PIECES; i++) {
  447.     done[i] = 0;
  448.   }
  449.   glLoadName(0);
  450.   drawContainer();
  451.   for (i = 0; i < HEIGHT; i++) {
  452.     for (j = 0; j < WIDTH; j++) {
  453.       piece = thePuzzle[i][j];
  454.       if (piece == 0)
  455.         continue;
  456.       if (done[piece])
  457.         continue;
  458.       done[piece] = 1;
  459.       glLoadName(piece);
  460.       if (piece == movingPiece) {
  461.         drawBox(piece, move_x, move_y);
  462.       } else {
  463.         drawBox(piece, j, i);
  464.       }
  465.     }
  466.   }
  467. }
  468.  
  469. void
  470. redraw(void)
  471. {
  472.   glMatrixMode(GL_PROJECTION);
  473.   glLoadIdentity();
  474.   gluPerspective(45, 1.0, 0.1, 100.0);
  475.  
  476.   drawAll();
  477.  
  478.   if (doubleBuffer)
  479.     glutSwapBuffers();
  480.   else
  481.     glFinish();
  482. }
  483.  
  484. void
  485. solidifyChain(struct puzzle *puzzle)
  486. {
  487.   int i;
  488.   char buf[256];
  489.  
  490.   i = 0;
  491.   while (puzzle->backptr) {
  492.     i++;
  493.     puzzle->backptr->solnptr = puzzle;
  494.     puzzle = puzzle->backptr;
  495.   }
  496.   sprintf(buf, "%d moves to complete!", i);
  497.   glutSetWindowTitle(buf);
  498. }
  499.  
  500. int
  501. addConfig(Config config, struct puzzle *back)
  502. {
  503.   unsigned hashvalue;
  504.   struct puzzle *newpiece;
  505.   struct puzzlelist *newlistentry;
  506.  
  507.   hashvalue = hash(config);
  508.  
  509.   newpiece = hashtable[hashvalue % HASHSIZE];
  510.   while (newpiece != NULL) {
  511.     if (newpiece->hashvalue == hashvalue) {
  512.       int i, j;
  513.  
  514.       for (i = 0; i < WIDTH; i++) {
  515.         for (j = 0; j < HEIGHT; j++) {
  516.           if (convert[config[j][i]] !=
  517.             convert[newpiece->pieces[j][i]])
  518.             goto nomatch;
  519.         }
  520.       }
  521.       return 0;
  522.     }
  523.   nomatch:
  524.     newpiece = newpiece->next;
  525.   }
  526.  
  527.   newpiece = (struct puzzle *) malloc(sizeof(struct puzzle));
  528.   newpiece->next = hashtable[hashvalue % HASHSIZE];
  529.   newpiece->hashvalue = hashvalue;
  530.   memcpy(newpiece->pieces, config, HEIGHT * WIDTH);
  531.   newpiece->backptr = back;
  532.   newpiece->solnptr = NULL;
  533.   hashtable[hashvalue % HASHSIZE] = newpiece;
  534.  
  535.   newlistentry = (struct puzzlelist *) malloc(sizeof(struct puzzlelist));
  536.   newlistentry->puzzle = newpiece;
  537.   newlistentry->next = NULL;
  538.  
  539.   if (lastentry) {
  540.     lastentry->next = newlistentry;
  541.   } else {
  542.     puzzles = newlistentry;
  543.   }
  544.   lastentry = newlistentry;
  545.  
  546.   if (back == NULL) {
  547.     startPuzzle = newpiece;
  548.   }
  549.   if (solution(config)) {
  550.     solidifyChain(newpiece);
  551.     return 1;
  552.   }
  553.   return 0;
  554. }
  555.  
  556. /* Checks if a space can move */
  557. int
  558. canmove0(Config pieces, int x, int y, int dir, Config newpieces)
  559. {
  560.   char piece;
  561.   int xadd, yadd;
  562.   int l, m;
  563.  
  564.   xadd = xadds[dir];
  565.   yadd = yadds[dir];
  566.  
  567.   if (x + xadd < 0 || x + xadd >= WIDTH ||
  568.     y + yadd < 0 || y + yadd >= HEIGHT)
  569.     return 0;
  570.   piece = pieces[y + yadd][x + xadd];
  571.   if (piece == 0)
  572.     return 0;
  573.   memcpy(newpieces, pieces, HEIGHT * WIDTH);
  574.   for (l = 0; l < WIDTH; l++) {
  575.     for (m = 0; m < HEIGHT; m++) {
  576.       if (newpieces[m][l] == piece)
  577.         newpieces[m][l] = 0;
  578.     }
  579.   }
  580.   xadd = -xadd;
  581.   yadd = -yadd;
  582.   for (l = 0; l < WIDTH; l++) {
  583.     for (m = 0; m < HEIGHT; m++) {
  584.       if (pieces[m][l] == piece) {
  585.         int newx, newy;
  586.  
  587.         newx = l + xadd;
  588.         newy = m + yadd;
  589.         if (newx < 0 || newx >= WIDTH ||
  590.           newy < 0 || newy >= HEIGHT)
  591.           return 0;
  592.         if (newpieces[newy][newx] != 0)
  593.           return 0;
  594.         newpieces[newy][newx] = piece;
  595.       }
  596.     }
  597.   }
  598.   return 1;
  599. }
  600.  
  601. /* Checks if a piece can move */
  602. int
  603. canmove(Config pieces, int x, int y, int dir, Config newpieces)
  604. {
  605.   int xadd, yadd;
  606.  
  607.   xadd = xadds[dir];
  608.   yadd = yadds[dir];
  609.  
  610.   if (x + xadd < 0 || x + xadd >= WIDTH ||
  611.     y + yadd < 0 || y + yadd >= HEIGHT)
  612.     return 0;
  613.   if (pieces[y + yadd][x + xadd] == pieces[y][x]) {
  614.     return canmove(pieces, x + xadd, y + yadd, dir, newpieces);
  615.   }
  616.   if (pieces[y + yadd][x + xadd] != 0)
  617.     return 0;
  618.   return canmove0(pieces, x + xadd, y + yadd, (dir + 2) % 4, newpieces);
  619. }
  620.  
  621. int
  622. generateNewConfigs(struct puzzle *puzzle)
  623. {
  624.   int i, j, k;
  625.   Config pieces;
  626.   Config newpieces;
  627.  
  628.   memcpy(pieces, puzzle->pieces, HEIGHT * WIDTH);
  629.   for (i = 0; i < WIDTH; i++) {
  630.     for (j = 0; j < HEIGHT; j++) {
  631.       if (pieces[j][i] == 0) {
  632.         for (k = 0; k < 4; k++) {
  633.           if (canmove0(pieces, i, j, k, newpieces)) {
  634.             if (addConfig(newpieces, puzzle))
  635.               return 1;
  636.           }
  637.         }
  638.       }
  639.     }
  640.   }
  641.   return 0;
  642. }
  643.  
  644. void
  645. freeSolutions(void)
  646. {
  647.   struct puzzlelist *nextpuz;
  648.   struct puzzle *puzzle, *next;
  649.   int i;
  650.  
  651.   while (puzzles) {
  652.     nextpuz = puzzles->next;
  653.     free((char *) puzzles);
  654.     puzzles = nextpuz;
  655.   }
  656.   lastentry = NULL;
  657.   for (i = 0; i < HASHSIZE; i++) {
  658.     puzzle = hashtable[i];
  659.     hashtable[i] = NULL;
  660.     while (puzzle) {
  661.       next = puzzle->next;
  662.       free((char *) puzzle);
  663.       puzzle = next;
  664.     }
  665.   }
  666.   startPuzzle = NULL;
  667. }
  668.  
  669. int
  670. continueSolving(void)
  671. {
  672.   struct puzzle *nextpuz;
  673.   int i, j;
  674.   int movedPiece;
  675.   int movedir;
  676.   int fromx, fromy;
  677.   int tox, toy;
  678.  
  679.   if (startPuzzle == NULL)
  680.     return 0;
  681.   if (startPuzzle->solnptr == NULL) {
  682.     freeSolutions();
  683.     return 0;
  684.   }
  685.   nextpuz = startPuzzle->solnptr;
  686.   movedPiece = 0;
  687.   movedir = 0;
  688.   for (i = 0; i < HEIGHT; i++) {
  689.     for (j = 0; j < WIDTH; j++) {
  690.       if (startPuzzle->pieces[i][j] != nextpuz->pieces[i][j]) {
  691.         if (startPuzzle->pieces[i][j]) {
  692.           movedPiece = startPuzzle->pieces[i][j];
  693.           fromx = j;
  694.           fromy = i;
  695.           if (i < HEIGHT - 1 && nextpuz->pieces[i + 1][j] == movedPiece) {
  696.             movedir = 3;
  697.           } else {
  698.             movedir = 2;
  699.           }
  700.           goto found_piece;
  701.         } else {
  702.           movedPiece = nextpuz->pieces[i][j];
  703.           if (i < HEIGHT - 1 &&
  704.             startPuzzle->pieces[i + 1][j] == movedPiece) {
  705.             fromx = j;
  706.             fromy = i + 1;
  707.             movedir = 1;
  708.           } else {
  709.             fromx = j + 1;
  710.             fromy = i;
  711.             movedir = 0;
  712.           }
  713.           goto found_piece;
  714.         }
  715.       }
  716.     }
  717.   }
  718.   glutSetWindowTitle("What!  No change?");
  719.   freeSolutions();
  720.   return 0;
  721.  
  722. found_piece:
  723.   if (!movingPiece) {
  724.     movingPiece = movedPiece;
  725.     move_x = fromx;
  726.     move_y = fromy;
  727.   }
  728.   move_x += xadds[movedir] * MOVE_SPEED;
  729.   move_y += yadds[movedir] * MOVE_SPEED;
  730.  
  731.   tox = fromx + xadds[movedir];
  732.   toy = fromy + yadds[movedir];
  733.  
  734.   if (move_x > tox - MOVE_SPEED / 2 && move_x < tox + MOVE_SPEED / 2 &&
  735.     move_y > toy - MOVE_SPEED / 2 && move_y < toy + MOVE_SPEED / 2) {
  736.     startPuzzle = nextpuz;
  737.     movingPiece = 0;
  738.   }
  739.   memcpy(thePuzzle, startPuzzle->pieces, HEIGHT * WIDTH);
  740.   changeState();
  741.   return 1;
  742. }
  743.  
  744. int
  745. solvePuzzle(void)
  746. {
  747.   struct puzzlelist *nextpuz;
  748.   char buf[256];
  749.   int i;
  750.  
  751.   if (solution(thePuzzle)) {
  752.     glutSetWindowTitle("Puzzle already solved!");
  753.     return 0;
  754.   }
  755.   addConfig(thePuzzle, NULL);
  756.   i = 0;
  757.  
  758.   while (puzzles) {
  759.     i++;
  760.     if (generateNewConfigs(puzzles->puzzle))
  761.       break;
  762.     nextpuz = puzzles->next;
  763.     free((char *) puzzles);
  764.     puzzles = nextpuz;
  765.   }
  766.   if (puzzles == NULL) {
  767.     freeSolutions();
  768.     sprintf(buf, "I can't solve it! (%d positions examined)", i);
  769.     glutSetWindowTitle(buf);
  770.     return 1;
  771.   }
  772.   return 1;
  773. }
  774.  
  775. int
  776. selectPiece(int mousex, int mousey)
  777. {
  778.   long hits;
  779.   GLuint selectBuf[1024];
  780.   GLuint closest;
  781.   GLuint dist;
  782.  
  783.   glSelectBuffer(1024, selectBuf);
  784.   (void) glRenderMode(GL_SELECT);
  785.   glInitNames();
  786.  
  787.   /* Because LoadName() won't work with no names on the stack */
  788.   glPushName(-1);
  789.  
  790.   glMatrixMode(GL_PROJECTION);
  791.   glLoadIdentity();
  792.   gluPickMatrix(mousex, H - mousey, 4, 4, viewport);
  793.   gluPerspective(45, 1.0, 0.1, 100.0);
  794.  
  795.   drawAll();
  796.  
  797.   hits = glRenderMode(GL_RENDER);
  798.   if (hits <= 0) {
  799.     return 0;
  800.   }
  801.   closest = 0;
  802.   dist = 4294967295;
  803.   while (hits) {
  804.     if (selectBuf[(hits - 1) * 4 + 1] < dist) {
  805.       dist = selectBuf[(hits - 1) * 4 + 1];
  806.       closest = selectBuf[(hits - 1) * 4 + 3];
  807.     }
  808.     hits--;
  809.   }
  810.   return closest;
  811. }
  812.  
  813. void
  814. nukePiece(int piece)
  815. {
  816.   int i, j;
  817.  
  818.   for (i = 0; i < HEIGHT; i++) {
  819.     for (j = 0; j < WIDTH; j++) {
  820.       if (thePuzzle[i][j] == piece) {
  821.         thePuzzle[i][j] = 0;
  822.       }
  823.     }
  824.   }
  825. }
  826.  
  827. void
  828. multMatrices(const GLfloat a[16], const GLfloat b[16], GLfloat r[16])
  829. {
  830.   int i, j;
  831.  
  832.   for (i = 0; i < 4; i++) {
  833.     for (j = 0; j < 4; j++) {
  834.       r[i * 4 + j] =
  835.         a[i * 4 + 0] * b[0 * 4 + j] +
  836.         a[i * 4 + 1] * b[1 * 4 + j] +
  837.         a[i * 4 + 2] * b[2 * 4 + j] +
  838.         a[i * 4 + 3] * b[3 * 4 + j];
  839.     }
  840.   }
  841. }
  842.  
  843. void
  844. makeIdentity(GLfloat m[16])
  845. {
  846.   m[0 + 4 * 0] = 1;
  847.   m[0 + 4 * 1] = 0;
  848.   m[0 + 4 * 2] = 0;
  849.   m[0 + 4 * 3] = 0;
  850.   m[1 + 4 * 0] = 0;
  851.   m[1 + 4 * 1] = 1;
  852.   m[1 + 4 * 2] = 0;
  853.   m[1 + 4 * 3] = 0;
  854.   m[2 + 4 * 0] = 0;
  855.   m[2 + 4 * 1] = 0;
  856.   m[2 + 4 * 2] = 1;
  857.   m[2 + 4 * 3] = 0;
  858.   m[3 + 4 * 0] = 0;
  859.   m[3 + 4 * 1] = 0;
  860.   m[3 + 4 * 2] = 0;
  861.   m[3 + 4 * 3] = 1;
  862. }
  863.  
  864. /*
  865.    ** inverse = invert(src)
  866.  */
  867. int
  868. invertMatrix(const GLfloat src[16], GLfloat inverse[16])
  869. {
  870.   int i, j, k, swap;
  871.   double t;
  872.   GLfloat temp[4][4];
  873.  
  874.   for (i = 0; i < 4; i++) {
  875.     for (j = 0; j < 4; j++) {
  876.       temp[i][j] = src[i * 4 + j];
  877.     }
  878.   }
  879.   makeIdentity(inverse);
  880.  
  881.   for (i = 0; i < 4; i++) {
  882.     /* 
  883.        ** Look for largest element in column */
  884.     swap = i;
  885.     for (j = i + 1; j < 4; j++) {
  886.       if (fabs(temp[j][i]) > fabs(temp[i][i])) {
  887.         swap = j;
  888.       }
  889.     }
  890.  
  891.     if (swap != i) {
  892.       /* 
  893.          ** Swap rows. */
  894.       for (k = 0; k < 4; k++) {
  895.         t = temp[i][k];
  896.         temp[i][k] = temp[swap][k];
  897.         temp[swap][k] = t;
  898.  
  899.         t = inverse[i * 4 + k];
  900.         inverse[i * 4 + k] = inverse[swap * 4 + k];
  901.         inverse[swap * 4 + k] = t;
  902.       }
  903.     }
  904.     if (temp[i][i] == 0) {
  905.       /* 
  906.          ** No non-zero pivot.  The matrix is singular, which
  907.          shouldn't ** happen.  This means the user gave us a
  908.          bad matrix. */
  909.       return 0;
  910.     }
  911.     t = temp[i][i];
  912.     for (k = 0; k < 4; k++) {
  913.       temp[i][k] /= t;
  914.       inverse[i * 4 + k] /= t;
  915.     }
  916.     for (j = 0; j < 4; j++) {
  917.       if (j != i) {
  918.         t = temp[j][i];
  919.         for (k = 0; k < 4; k++) {
  920.           temp[j][k] -= temp[i][k] * t;
  921.           inverse[j * 4 + k] -= inverse[i * 4 + k] * t;
  922.         }
  923.       }
  924.     }
  925.   }
  926.   return 1;
  927. }
  928.  
  929. /*
  930.    ** This is a screwball function.  What it does is the following:
  931.    ** Given screen x and y coordinates, compute the corresponding object space 
  932.    **   x and y coordinates given that the object space z is 0.9 + OFFSETZ.
  933.    ** Since the tops of (most) pieces are at z = 0.9 + OFFSETZ, we use that 
  934.    **   number.
  935.  */
  936. int
  937. computeCoords(int piece, int mousex, int mousey,
  938.   GLfloat * selx, GLfloat * sely)
  939. {
  940.   GLfloat modelMatrix[16];
  941.   GLfloat projMatrix[16];
  942.   GLfloat finalMatrix[16];
  943.   GLfloat in[4];
  944.   GLfloat a, b, c, d;
  945.   GLfloat top, bot;
  946.   GLfloat z;
  947.   GLfloat w;
  948.   GLfloat height;
  949.  
  950.   if (piece == 0)
  951.     return 0;
  952.   height = zsize[piece] - 0.1 + OFFSETZ;
  953.  
  954.   glGetFloatv(GL_PROJECTION_MATRIX, projMatrix);
  955.   glGetFloatv(GL_MODELVIEW_MATRIX, modelMatrix);
  956.   multMatrices(modelMatrix, projMatrix, finalMatrix);
  957.   if (!invertMatrix(finalMatrix, finalMatrix))
  958.     return 0;
  959.  
  960.   in[0] = (2.0 * (mousex - viewport[0]) / viewport[2]) - 1;
  961.   in[1] = (2.0 * ((H - mousey) - viewport[1]) / viewport[3]) - 1;
  962.  
  963.   a = in[0] * finalMatrix[0 * 4 + 2] +
  964.     in[1] * finalMatrix[1 * 4 + 2] +
  965.     finalMatrix[3 * 4 + 2];
  966.   b = finalMatrix[2 * 4 + 2];
  967.   c = in[0] * finalMatrix[0 * 4 + 3] +
  968.     in[1] * finalMatrix[1 * 4 + 3] +
  969.     finalMatrix[3 * 4 + 3];
  970.   d = finalMatrix[2 * 4 + 3];
  971.  
  972.   /* 
  973.      ** Ok, now we need to solve for z: **   (a + b z) / (c + d 
  974.  
  975.      z) = height. ** ("height" is the height in object space we 
  976.  
  977.      want to solve z for) ** ** ==>  a + b z = height c +
  978.      height d z **      bz - height d z = height c - a ** z =
  979.      (height c - a) / (b - height d) */
  980.   top = height * c - a;
  981.   bot = b - height * d;
  982.   if (bot == 0.0)
  983.     return 0;
  984.  
  985.   z = top / bot;
  986.  
  987.   /* 
  988.      ** Ok, no problem. ** Now we solve for x and y.  We know
  989.      that w = c + d z, so we compute it. */
  990.   w = c + d * z;
  991.  
  992.   /* 
  993.      ** Now for x and y: */
  994.   *selx = (in[0] * finalMatrix[0 * 4 + 0] +
  995.     in[1] * finalMatrix[1 * 4 + 0] +
  996.     z * finalMatrix[2 * 4 + 0] +
  997.     finalMatrix[3 * 4 + 0]) / w - OFFSETX;
  998.   *sely = (in[0] * finalMatrix[0 * 4 + 1] +
  999.     in[1] * finalMatrix[1 * 4 + 1] +
  1000.     z * finalMatrix[2 * 4 + 1] +
  1001.     finalMatrix[3 * 4 + 1]) / w - OFFSETY;
  1002.   return 1;
  1003. }
  1004.  
  1005. static int selected;
  1006. static int selectx, selecty;
  1007. static float selstartx, selstarty;
  1008.  
  1009. void
  1010. grabPiece(int piece, float selx, float sely)
  1011. {
  1012.   int hit;
  1013.  
  1014.   selectx = selx;
  1015.   selecty = sely;
  1016.   if (selectx < 0 || selecty < 0 || selectx >= WIDTH || selecty >= HEIGHT) {
  1017.     return;
  1018.   }
  1019.   hit = thePuzzle[selecty][selectx];
  1020.   if (hit != piece)
  1021.     return;
  1022.   if (hit) {
  1023.     movingPiece = hit;
  1024.     while (selectx > 0 && thePuzzle[selecty][selectx - 1] == movingPiece) {
  1025.       selectx--;
  1026.     }
  1027.     while (selecty > 0 && thePuzzle[selecty - 1][selectx] == movingPiece) {
  1028.       selecty--;
  1029.     }
  1030.     move_x = selectx;
  1031.     move_y = selecty;
  1032.     selected = 1;
  1033.     selstartx = selx;
  1034.     selstarty = sely;
  1035.   } else {
  1036.     selected = 0;
  1037.   }
  1038.   changeState();
  1039. }
  1040.  
  1041. void
  1042. moveSelection(float selx, float sely)
  1043. {
  1044.   float deltax, deltay;
  1045.   int dir;
  1046.   Config newpieces;
  1047.  
  1048.   if (!selected)
  1049.     return;
  1050.   deltax = selx - selstartx;
  1051.   deltay = sely - selstarty;
  1052.  
  1053.   if (fabs(deltax) > fabs(deltay)) {
  1054.     deltay = 0;
  1055.     if (deltax > 0) {
  1056.       if (deltax > 1)
  1057.         deltax = 1;
  1058.       dir = 2;
  1059.     } else {
  1060.       if (deltax < -1)
  1061.         deltax = -1;
  1062.       dir = 0;
  1063.     }
  1064.   } else {
  1065.     deltax = 0;
  1066.     if (deltay > 0) {
  1067.       if (deltay > 1)
  1068.         deltay = 1;
  1069.       dir = 3;
  1070.     } else {
  1071.       if (deltay < -1)
  1072.         deltay = -1;
  1073.       dir = 1;
  1074.     }
  1075.   }
  1076.   if (canmove(thePuzzle, selectx, selecty, dir, newpieces)) {
  1077.     move_x = deltax + selectx;
  1078.     move_y = deltay + selecty;
  1079.     if (deltax > 0.5) {
  1080.       memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
  1081.       selectx++;
  1082.       selstartx++;
  1083.     } else if (deltax < -0.5) {
  1084.       memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
  1085.       selectx--;
  1086.       selstartx--;
  1087.     } else if (deltay > 0.5) {
  1088.       memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
  1089.       selecty++;
  1090.       selstarty++;
  1091.     } else if (deltay < -0.5) {
  1092.       memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
  1093.       selecty--;
  1094.       selstarty--;
  1095.     }
  1096.   } else {
  1097.     if (deltay > 0 && thePuzzle[selecty][selectx] == 10 &&
  1098.       selectx == 1 && selecty == 3) {
  1099.       /* Allow visual movement of solution piece outside of the 
  1100.  
  1101.          box */
  1102.       move_x = selectx;
  1103.       move_y = sely - selstarty + selecty;
  1104.     } else {
  1105.       move_x = selectx;
  1106.       move_y = selecty;
  1107.     }
  1108.   }
  1109. }
  1110.  
  1111. void
  1112. dropSelection(void)
  1113. {
  1114.   if (!selected)
  1115.     return;
  1116.   movingPiece = 0;
  1117.   selected = 0;
  1118.   changeState();
  1119. }
  1120.  
  1121. static int left_mouse, middle_mouse;
  1122. static int mousex, mousey;
  1123. static int solving;
  1124. static int spinning;
  1125. static float lastquat[4];
  1126. static int sel_piece;
  1127.  
  1128. static void
  1129. Reshape(int width, int height)
  1130. {
  1131.  
  1132.   W = width;
  1133.   H = height;
  1134.   glViewport(0, 0, W, H);
  1135.   glGetIntegerv(GL_VIEWPORT, viewport);
  1136. }
  1137.  
  1138. void
  1139. toggleSolve(void)
  1140. {
  1141.     if (solving) {
  1142.       freeSolutions();
  1143.       solving = 0;
  1144.       glutChangeToMenuEntry(1, "Solving", 1);
  1145.       glutSetWindowTitle("glpuzzle");
  1146.       movingPiece = 0;
  1147.     } else {
  1148.       glutChangeToMenuEntry(1, "Stop solving", 1);
  1149.       glutSetWindowTitle("Solving...");
  1150.       if (solvePuzzle()) {
  1151.         solving = 1;
  1152.       }
  1153.     }
  1154.     changeState();
  1155.     glutPostRedisplay();
  1156. }
  1157.  
  1158. void reset(void)
  1159. {
  1160.     if (solving) {
  1161.       freeSolutions();
  1162.       solving = 0;
  1163.       glutChangeToMenuEntry(1, "Solving", 1);
  1164.       glutSetWindowTitle("glpuzzle");
  1165.       movingPiece = 0;
  1166.       changeState();
  1167.     }
  1168.     memcpy(thePuzzle, startConfig, HEIGHT * WIDTH);
  1169.     glutPostRedisplay();
  1170. }
  1171.  
  1172. void
  1173. keyboard(unsigned char c, int x, int y)
  1174. {
  1175.   int piece;
  1176.  
  1177.   switch (c) {
  1178.   case 27:
  1179.     exit(0);
  1180.     break;
  1181.   case 'D':
  1182.   case 'd':
  1183.     if (solving) {
  1184.       freeSolutions();
  1185.       solving = 0;
  1186.       glutChangeToMenuEntry(1, "Solving", 1);
  1187.       glutSetWindowTitle("glpuzzle");
  1188.       movingPiece = 0;
  1189.       changeState();
  1190.     }
  1191.     piece = selectPiece(x, y);
  1192.     if (piece) {
  1193.       nukePiece(piece);
  1194.     }
  1195.     glutPostRedisplay();
  1196.     break;
  1197.   case 'R':
  1198.   case 'r':
  1199.     reset();
  1200.     break;
  1201.   case 'S':
  1202.   case 's':
  1203.     toggleSolve();
  1204.     break;
  1205.   case 'b':
  1206.   case 'B':
  1207.     depth = 1 - depth;
  1208.     if (depth) {
  1209.       glEnable(GL_DEPTH_TEST);
  1210.     } else {
  1211.       glDisable(GL_DEPTH_TEST);
  1212.     }
  1213.     glutPostRedisplay();
  1214.     break;
  1215.   default:
  1216.     break;
  1217.   }
  1218. }
  1219.  
  1220. void
  1221. motion(int x, int y)
  1222. {
  1223.   float selx, sely;
  1224.  
  1225.   if (middle_mouse && !left_mouse) {
  1226.     if (mousex != x || mousey != y) {
  1227.       trackball(lastquat,
  1228.         (2.0*mousex - W) / W,
  1229.         (H - 2.0*mousey) / H,
  1230.         (2.0*x - W) / W,
  1231.         (H - 2.0*y) / H);
  1232.       spinning = 1;
  1233.     } else {
  1234.       spinning = 0;
  1235.     }
  1236.     changeState();
  1237.   } else {
  1238.     computeCoords(sel_piece, x, y, &selx, &sely);
  1239.     moveSelection(selx, sely);
  1240.   }
  1241.   mousex = x;
  1242.   mousey = y;
  1243.   glutPostRedisplay();
  1244. }
  1245.  
  1246. void
  1247. mouse(int b, int s, int x, int y)
  1248. {
  1249.   float selx, sely;
  1250.  
  1251.   mousex = x;
  1252.   mousey = y;
  1253.   curX = x;
  1254.   curY = y;
  1255.   if (s == GLUT_DOWN) {
  1256.     switch (b) {
  1257.     case GLUT_LEFT_BUTTON:
  1258.       if (solving) {
  1259.         freeSolutions();
  1260.         solving = 0;
  1261.       glutChangeToMenuEntry(1, "Solving", 1);
  1262.         glutSetWindowTitle("glpuzzle");
  1263.         movingPiece = 0;
  1264.       }
  1265.       left_mouse = GL_TRUE;
  1266.       sel_piece = selectPiece(mousex, mousey);
  1267.       if (computeCoords(sel_piece, mousex, mousey, &selx, &sely)) {
  1268.         grabPiece(sel_piece, selx, sely);
  1269.       }
  1270.       glutPostRedisplay();
  1271.       break;
  1272.     case GLUT_MIDDLE_BUTTON:
  1273.       middle_mouse = GL_TRUE;
  1274.       glutPostRedisplay();
  1275.       break;
  1276.     }
  1277.   } else {
  1278.     switch (b) {
  1279.     case GLUT_LEFT_BUTTON:
  1280.       left_mouse = GL_FALSE;
  1281.       dropSelection();
  1282.       glutPostRedisplay();
  1283.       break;
  1284.     case GLUT_MIDDLE_BUTTON:
  1285.       middle_mouse = GL_FALSE;
  1286.       glutPostRedisplay();
  1287.       break;
  1288.     }
  1289.   }
  1290.   motion(x, y);
  1291. }
  1292.  
  1293. void
  1294. animate(void)
  1295. {
  1296.   if (spinning) {
  1297.     add_quats(lastquat, curquat, curquat);
  1298.   }
  1299.   glutPostRedisplay();
  1300.   if (solving) {
  1301.     if (!continueSolving()) {
  1302.       solving = 0;
  1303.       glutChangeToMenuEntry(1, "Solving", 1);
  1304.       glutSetWindowTitle("glpuzzle");
  1305.     }
  1306.   }
  1307.   if (!solving && !spinning && !visible) {
  1308.     glutIdleFunc(NULL);
  1309.   }
  1310. }
  1311.  
  1312. void
  1313. changeState(void)
  1314. {
  1315.   if (visible) {
  1316.     if (!solving && !spinning) {
  1317.       glutIdleFunc(NULL);
  1318.     } else {
  1319.       glutIdleFunc(animate);
  1320.     }
  1321.   } else {
  1322.     glutIdleFunc(NULL);
  1323.   }
  1324. }
  1325.  
  1326. void
  1327. init(void)
  1328. {
  1329.   static float lmodel_ambient[] =
  1330.   {0.0, 0.0, 0.0, 0.0};
  1331.   static float lmodel_twoside[] =
  1332.   {GL_FALSE};
  1333.   static float lmodel_local[] =
  1334.   {GL_FALSE};
  1335.   static float light0_ambient[] =
  1336.   {0.1, 0.1, 0.1, 1.0};
  1337.   static float light0_diffuse[] =
  1338.   {1.0, 1.0, 1.0, 0.0};
  1339.   static float light0_position[] =
  1340.   {0.8660254, 0.5, 1, 0};
  1341.   static float light0_specular[] =
  1342.   {0.0, 0.0, 0.0, 0.0};
  1343.   static float bevel_mat_ambient[] =
  1344.   {0.0, 0.0, 0.0, 1.0};
  1345.   static float bevel_mat_shininess[] =
  1346.   {40.0};
  1347.   static float bevel_mat_specular[] =
  1348.   {0.0, 0.0, 0.0, 0.0};
  1349.   static float bevel_mat_diffuse[] =
  1350.   {1.0, 0.0, 0.0, 0.0};
  1351.  
  1352.   glEnable(GL_CULL_FACE);
  1353.   glCullFace(GL_BACK);
  1354.   glEnable(GL_DEPTH_TEST);
  1355.   glClearDepth(1.0);
  1356.  
  1357.   glClearColor(0.5, 0.5, 0.5, 0.0);
  1358.   glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);
  1359.   glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);
  1360.   glLightfv(GL_LIGHT0, GL_SPECULAR, light0_specular);
  1361.   glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
  1362.   glEnable(GL_LIGHT0);
  1363.  
  1364.   glLightModelfv(GL_LIGHT_MODEL_LOCAL_VIEWER, lmodel_local);
  1365.   glLightModelfv(GL_LIGHT_MODEL_TWO_SIDE, lmodel_twoside);
  1366.   glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lmodel_ambient);
  1367.   glEnable(GL_LIGHTING);
  1368.  
  1369.   glMaterialfv(GL_FRONT, GL_AMBIENT, bevel_mat_ambient);
  1370.   glMaterialfv(GL_FRONT, GL_SHININESS, bevel_mat_shininess);
  1371.   glMaterialfv(GL_FRONT, GL_SPECULAR, bevel_mat_specular);
  1372.   glMaterialfv(GL_FRONT, GL_DIFFUSE, bevel_mat_diffuse);
  1373.  
  1374.   glColorMaterial(GL_FRONT_AND_BACK, GL_DIFFUSE);
  1375.   glEnable(GL_COLOR_MATERIAL);
  1376.   glShadeModel(GL_FLAT);
  1377.  
  1378.   trackball(curquat, 0.0, 0.0, 0.0, 0.0);
  1379.   srandom(time(NULL));
  1380. }
  1381.  
  1382. static void
  1383. Usage(void)
  1384. {
  1385.   printf("Usage: puzzle [-s]\n");
  1386.   printf("   -s:  Run in single buffered mode\n");
  1387.   exit(-1);
  1388. }
  1389.  
  1390. void
  1391. visibility(int v)
  1392. {
  1393.   if (v == GLUT_VISIBLE) {
  1394.     visible = 1;
  1395.   } else {
  1396.     visible = 0;
  1397.   }
  1398.   changeState();
  1399. }
  1400.  
  1401. void
  1402. menu(int choice)
  1403. {
  1404.    switch(choice) {
  1405.    case 1:
  1406.       toggleSolve();
  1407.       break;
  1408.    case 2:
  1409.       reset();
  1410.       break;
  1411.    case 3:
  1412.       exit(0);
  1413.       break;
  1414.    }
  1415. }
  1416.  
  1417. void
  1418. main(int argc, char **argv)
  1419. {
  1420.   long i;
  1421.  
  1422.   glutInit(&argc, argv);
  1423.   for (i = 1; i < argc; i++) {
  1424.     if (argv[i][0] == '-') {
  1425.       switch (argv[i][1]) {
  1426.       case 's':
  1427.         doubleBuffer = 0;
  1428.         break;
  1429.       default:
  1430.         Usage();
  1431.       }
  1432.     } else {
  1433.       Usage();
  1434.     }
  1435.   }
  1436.  
  1437.   glutInitWindowSize(W, H);
  1438.   if (doubleBuffer) {
  1439.     glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
  1440.   } else {
  1441.     glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_SINGLE | GLUT_MULTISAMPLE);
  1442.   }
  1443.  
  1444.   glutCreateWindow("glpuzzle");
  1445.  
  1446.   init();
  1447.  
  1448.   glGetIntegerv(GL_VIEWPORT, viewport);
  1449.  
  1450.   printf("\n");
  1451.   printf("r   Reset puzzle\n");
  1452.   printf("s   Solve puzzle (may take a few seconds to compute)\n");
  1453.   printf("d   Destroy a piece - makes the puzzle easier\n");
  1454.   printf("b   Toggles the depth buffer on and off\n");
  1455.   printf("\n");
  1456.   printf("Left mouse moves pieces\n");
  1457.   printf("Middle mouse spins the puzzle\n");
  1458.   printf("Right mouse has menu\n");
  1459.  
  1460.   glutReshapeFunc(Reshape);
  1461.   glutDisplayFunc(redraw);
  1462.   glutKeyboardFunc(keyboard);
  1463.   glutMotionFunc(motion);
  1464.   glutMouseFunc(mouse);
  1465.   glutVisibilityFunc(visibility);
  1466.   glutCreateMenu(menu);
  1467.   glutAddMenuEntry("Solve", 1);
  1468.   glutAddMenuEntry("Reset", 2);
  1469.   glutAddMenuEntry("Quit", 3);
  1470.   glutAttachMenu(GLUT_RIGHT_BUTTON);
  1471.   glutMainLoop();
  1472. }
  1473.